package com.example.demo6;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class MyLinkedList<E> {
    private int size;

    /**
     * 定义了一个私有的内部类,作为列表的节点
     *
     * @param <E>
     */
    public static class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    public Node<E> add() {
        Node<E> head = null;
        Scanner sc = new Scanner(System.in);
        while (true) {
            System.out.print("请输入要添加的元素：");
            String data = sc.next();
            if (data.equals("exit")) {
                break;
            }
            // 判断head是否位头节点
            if (head == null) {
                // 说明是第一个节点
                head = new Node(data, null);
                size++;
            } else {
                // 往后面去插入(尾插法)
                Node<E> temp = head;
                // 让temp走到尾节点
                while (temp.next != null) { // 只要temp.next不为空,就说明还没有到尾节点就一直循环
                    // 让temp往后走
                    temp = temp.next;
                }
                // 把当前节点创建出来
                temp.next = new Node(data, null);
                size++;
            }
        }
        return head;
    }

    /**
     * 反转链表
     *
     * @param head  头节点
     * @param left  反转的起始位置
     * @param right 反转的结束位置
     * @return 反转后的头节点
     */
    // 1 2 3 4 5 6    left = 2  right = 5
    public Node<E> reverse(Node<E> head, int left, int right) {
        if (head == null || left < 1 || left > size || right < 1 || right > size || left == right || left > right) {
            return head;
        }

        // 1.找出左节点的起始位置
        // 2.左节点遍历到右节点,然后把数据存入集合
        Node<E> first = head; // 把头节点暂存一份到first中防止在便力量的过程中修改了头指针
        Node<E> mark = null; // 标记左节点
        List<E> data = new ArrayList<>();
        int index = 0;
        while (head != null) {
            index++;
            if (index == left) {
                mark = head; // 找到左节点的位置
            }

            if (index >= left && index <= right) {
                // 说明在我们需要的区间内,把数据存入集合中
                data.add(head.data);
            }

            // 不用遍历全部的列表,当下标等于右节点就跳出循环,以为我们需要的数据都在这个区间内,后面就不在需要了
            if (index == right) break;

            // 指向下一个节点
            head = head.next;
        }

        // 2.倒序遍历集合
        for (int i = data.size() - 1; i >= 0; i--) {
            E e = data.get(i);
            // 把数据存入当前节点
            mark.data = e;
            // 指向下一个节点
            mark = mark.next;

        }
        return first;
    }

    /**
     * 遍历链表
     *
     * @param head 头节点
     */
    public void forEach(Node<E> head) {
        if (head == null) {
            System.out.println(head);
            return;
        }
        while (head != null) {
            System.out.print(head.data + " ");
            // 让头指针指向下一个节点
            head = head.next;
        }
    }
}
